package leetcode_400;

import helpclass.ListNode;

/**
 *@author 周杨
 *LinkedListRandomNode_382 返回链表里的随机一个节点
 *describe:用size随机数 每次顺序遍历 AC 100%
 *2018年7月11日 下午12:10:46
 */
public class LinkedListRandomNode_382 {
	private ListNode node; //need base node
    private int size; //keep track of list size

    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public LinkedListRandomNode_382(ListNode head) {
        //Abuse local variables as much as possible, and crazy initialization of "node=head" in loop
        for (node = head; head != null; head = head.next) {  
            ++size; 
        }
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode result = node;
				//"for loop" initialzation of an integer
        for (int randIndex = (int) (Math.random() * size); randIndex > 0; --randIndex) {
            result = result.next;
        }
        return result.val;
    }
}
